/*-------------------------------------------------------------------------
 - Copyright (c) 2024-2025 [XD-AMCC TEAM]
 - [XD-AMCC] is licensed under Mulan PSL v2.
 - You can use this software according to the terms and conditions of the Mulan PSL v2.
 - You may obtain a copy of Mulan PSL v2 at:
 -          http://license.coscl.org.cn/MulanPSL2
 - THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES
 - OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
 - TO NON-INFRINGEMENT, MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
 - See the Mulan PSL v2 for more details.
 ------------------------------------------------------------------------*/


/**
 * @brief Implement a double linked circular list and its iterator,
 *        both are generic types.
 *
 * @author  WXQ#XDU
 * @date    2024.11
 */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>  // for malloc, free

#include "../include/amcc_list.h"


#if defined( DEBUG_LIST )

#define  debugPrintf(fmt, ...)  printf(fmt, ## __VA_ARGS__)
#define  debugPrint_list_appdata(pList, fmt, ...)                   \
         do { t_list_node * node = (pList)->holder.pNext;           \
              printf("DEBUG: list length is %d " fmt ,              \
                        (pList)->length, ## __VA_ARGS__);           \
              if( (pList)->length > 0)                              \
                  printf("    first=%p,  last=%p\n",                \
                        (pList)->holder.pNext->pValue,              \
                        (pList)->holder.pPrev->pValue);             \
              for (int idx = 0; idx < (pList)->length; ++idx) {     \
                  printf(   "    DEBUG: prev-value %p, "            \
                            "node-value %p, next-value %p\n",       \
                        node->pPrev->pValue, node->pValue,          \
                        node->pNext->pValue);                       \
                  node = node->pNext;                               \
              }                                                     \
              printf("\n");                                         \
         } while(0)
#else

#define  debugPrintf(fmt, ...)
#define  debugPrint_list_appdata(pList, fmt, ...)

#endif

bool list_has_freefunc(t_list_ptr pThis) {
    return NULL != pThis->fp_free_appdata;
}

void list_init(t_list_ptr pThis, t_listfunc_free_appdata fp_free) {
    assert( NULL != pThis );

    pThis->length = 0;
    pThis->holder.pPrev = pThis->holder.pNext = NULL;
    pThis->fp_free_appdata = fp_free;
}

t_list_ptr list_new(t_listfunc_free_appdata fp_free) {
    t_list_ptr pThis = (t_list_ptr)calloc(1, sizeof(t_list));
    if (NULL != pThis) {
        list_init(pThis, fp_free);
    }
    return pThis;
}

static void do_list_clean(t_list_ptr pThis, bool isFreeAppData) {
    if ( list_is_empty(pThis) )
        return ;
    t_listfunc_free_appdata fp_free_appdata = pThis->fp_free_appdata;
    t_list_node * pNode = pThis->holder.pNext;
    t_list_node * next = NULL;

    for (int i=0; i<pThis->length; ++i) {
        next = pNode->pNext;
        if (isFreeAppData && NULL != fp_free_appdata)
            fp_free_appdata ( pNode->pValue );
        free ( pNode );
        if (NULL == (pNode = next))  break;
    }

    list_init (pThis, fp_free_appdata);
}

void list_clean(t_list_ptr pThis) {
    do_list_clean(pThis, true);
}

void list_destroy(t_list_ptr pThis) {
    do_list_clean(pThis, true);
    free(pThis);
}

void list_clean_without_appdata(t_list_ptr pThis) {
    do_list_clean(pThis, false);
}

bool list_is_empty(t_list_ptr pThis) {
    return ((NULL == (pThis)) || (pThis)->length <= 0);
}

int list_size(t_list_ptr pThis) {
    if (NULL == pThis) return 0;
    return pThis->length;
}


t_list_app_value list_get_value(t_list_ptr pThis, int index) {
    if ( list_is_empty(pThis) || index < 0 || (index >= pThis->length) )
        return NULL;

    int  middelIdx = pThis->length / 2;  // locate ONLY in half of the set
    if ( index < middelIdx ) {
        // locate from the head, in the 1st half of the set
        t_list_node* pNode = pThis->holder.pNext;
        for (int i = 0; i < middelIdx; ++i) {
            if(i == index)
                return pNode->pValue;
            pNode = pNode->pNext;
        }
    } else {
        // locate from the tail, in the 2nd half of the set
        t_list_node* pNode = pThis->holder.pPrev;
        for (int i=pThis->length-1; i >= middelIdx; --i) {
            if(i == index)
                return pNode->pValue;
            pNode = pNode->pPrev;
        }
    }

    return NULL; // NOT REACHED HERE !!!
}


t_list_app_value  list_get_first_value(t_list_ptr pThis){
    if ( list_is_empty(pThis) )
        return NULL;
    else
        return pThis->holder.pNext->pValue;
}


t_list_app_value  list_get_last_value(t_list_ptr pThis){
    if ( list_is_empty(pThis) )
        return NULL;
    else
        return pThis->holder.pPrev->pValue;
}


int list_foreach(t_list_ptr pThis, t_listfunc_visit_appdata fp_visit, void* user_data) {
    if ( list_is_empty(pThis) || NULL == fp_visit )
        return 0;

    t_list_node* pNode = pThis->holder.pNext;  // the first element
    for (int res, i = 0 ; i < pThis->length ; ++i) {
        res = fp_visit(pNode->pValue, user_data);
        if (res != 0)
            return res;
        pNode = pNode->pNext;
        if (NULL == pNode)  break;
    }

    return 0;
}


int list_foreach_reverse(t_list_ptr pThis, t_listfunc_visit_appdata fp_visit, void* user_data) {
    if ( list_is_empty(pThis) || NULL == fp_visit )
        return 0;

    t_list_node* pNode = pThis->holder.pPrev;  // the last element
    for (int res, i = 0 ; i < pThis->length ; ++i) {
        res = fp_visit(pNode->pValue, user_data);
        if (res != 0)
            return res;
        pNode = pNode->pPrev;
        if (NULL == pNode)  break;
    }

    return 0;
}


t_list_app_value * list_to_array(t_list_ptr pThis) {
    if( list_is_empty(pThis) )
        return NULL;
    t_list_app_value * array = (t_list_app_value*)calloc(
            pThis->length, sizeof(t_list_app_value) );
    if (NULL == array)
        return NULL;

    t_list_node * pNode = pThis->holder.pNext;
    for (int i = 0 ; i < pThis->length ; ++i) {
        array[i] = pNode->pValue;
        pNode = pNode->pNext;
        if (NULL == pNode)  break;
    }
    return array;
}


t_list_node * list_append(t_list_ptr pThis, t_list_app_value pAppData) {
    //assert( NULL != pThis );
    t_list_node* pNode = (t_list_node*)calloc(1, sizeof(t_list_node));
    if (NULL == pNode)
        return NULL;
    pNode->pValue = pAppData;

    if ( list_is_empty(pThis) ) {  // for the first element
        pThis->holder.pPrev = pNode;
        pThis->holder.pNext = pNode;
        pNode->pNext = pNode;
        pNode->pPrev = pNode;
    } else {
        t_list_node* pLast = pThis->holder.pPrev; // last node
        pNode->pPrev = pLast;
        pNode->pNext = pThis->holder.pNext;       // first node
        pLast->pNext = pNode;
        pThis->holder.pPrev = pNode;
        pThis->holder.pNext->pPrev = pNode;
    }

    ++ ((pThis)->length);
    debugPrint_list_appdata(pThis, "After append %p\n", pNode->pValue);
    return pNode;
}


t_list_node* list_prepend(t_list_ptr pThis, t_list_app_value pAppData) {
    assert( NULL != pThis );
    t_list_node* pNode = (t_list_node*)calloc(1, sizeof(t_list_node));
    if (NULL == pNode)
        return NULL;
    pNode->pValue = pAppData;

    if ( list_is_empty(pThis) ) {  // for the first element
        pThis->holder.pPrev = pNode;
        pThis->holder.pNext = pNode;
        pNode->pNext = pNode;
        pNode->pPrev = pNode;
    } else {
        t_list_node* pFirst = pThis->holder.pNext; // first node
        pNode->pNext  = pFirst;
        pNode->pPrev  = pThis->holder.pPrev;       // last node
        pFirst->pPrev = pNode;
        pThis->holder.pNext = pNode;
        pThis->holder.pPrev->pNext =  pNode;
    }

    ++ ((pThis)->length);
    debugPrint_list_appdata(pThis, "After PreAppend %p\n", pNode->pValue);
    return pNode;
}


t_list_app_value list_remove_first(t_list_ptr pThis) {
    t_list_app_value ret = list_get_first_value(pThis);
    list_remove_range(pThis, 0, 1);
    return ret;
}

t_list_app_value list_remove_last(t_list_ptr pThis) {
    t_list_app_value ret = list_get_last_value(pThis);
    list_remove_range(pThis, list_size(pThis) - 1, INT_MAX);
    return ret;
}


int list_remove_range(t_list_ptr pThis, int indexFirst, int indexEnd) {
    if ( NULL == pThis  || indexFirst < 0 || indexEnd < 0
         || indexFirst >= pThis->length || indexFirst >= indexEnd )
    {
        return 0;
    }

    t_listfunc_free_appdata fp_free_appdata = pThis->fp_free_appdata;
    if (indexEnd > pThis->length)
        indexEnd = pThis -> length;

    // goto first node to be removed, and save its prev
    t_list_node * pTobeRemoved = pThis->holder.pNext;
    t_list_node * prevOfFirstRemoved = pThis->holder.pPrev;
    for (int idx = 0; idx < indexFirst; ++idx) {
        prevOfFirstRemoved = pTobeRemoved;
        pTobeRemoved = pTobeRemoved->pNext;
    }
    debugPrintf("    Prev of 1st removed %p\n", prevOfFirstRemoved->pValue);

    for (int idx = indexFirst; idx < indexEnd; ++idx) {
        t_list_node * pNext = pTobeRemoved->pNext;
        debugPrintf("\t delete %p, next %p\n", pTobeRemoved->pValue, pNext->pValue);
        if(NULL != fp_free_appdata) fp_free_appdata ( pTobeRemoved->pValue );
        free( pTobeRemoved );
        pTobeRemoved = pNext;
        --(pThis->length);
    }
    // At here, pTobeRemoved points to nodes[indeEnd] of input list

    // remove first node to end of list
    if ( 0 == pThis->length) {
        pThis->length = 0;
        pThis->holder.pPrev = pThis->holder.pNext = NULL;
    } else {
        debugPrintf("    Prev of 1st removed %p\n", prevOfFirstRemoved->pValue);
        debugPrintf("   next to last removed %p\n", pTobeRemoved->pValue);

        if ( 0 == indexFirst )
            pThis->holder.pNext = pTobeRemoved;
        if ( indexEnd >= pThis->length)
            pThis->holder.pPrev = prevOfFirstRemoved;
        prevOfFirstRemoved->pNext = pTobeRemoved;
        pTobeRemoved->pPrev = prevOfFirstRemoved;
    }

    debugPrint_list_appdata(pThis, "After remove from %d to %d\n", indexFirst, indexEnd);
    assert( pThis->length >= 0 );
    return indexEnd - indexFirst;
}

// remove the specified node
t_list_app_value list_remove(t_list_ptr pThis, t_list_node_ptr nodeTobeRemove) {
    if (NULL == pThis || NULL == nodeTobeRemove || pThis->length <= 0)
        return NULL;
//Step 1: modify inner structure
    if (nodeTobeRemove == pThis->holder.pNext) {  // if: remove first node
        //reset: tail.next and new-head point to 2nd node.
        pThis->holder.pPrev->pNext = pThis->holder.pNext = nodeTobeRemove->pNext ;
    }
    if (nodeTobeRemove == pThis->holder.pPrev) {  // if: remove last  node
        //reset: head.prev and new-tail point to -2nd node
        pThis->holder.pNext->pPrev = pThis->holder.pPrev = nodeTobeRemove->pPrev ;
    }

    nodeTobeRemove->pNext->pPrev = nodeTobeRemove->pPrev;
    nodeTobeRemove->pPrev->pNext = nodeTobeRemove->pNext;
    --(pThis->length);
    if (0 == pThis->length) {
        pThis->length = 0;
        pThis->holder.pPrev = pThis->holder.pNext = NULL;
    }

// Step 2: destroy node
    t_listfunc_free_appdata fp_free_appdata = pThis->fp_free_appdata;
    t_list_app_value appValue = nodeTobeRemove->pValue;
    if (NULL != fp_free_appdata) fp_free_appdata ( nodeTobeRemove->pValue );
    free( nodeTobeRemove );

    return appValue;
}


int list_remove_if(t_list_ptr pThis, t_listfunc_predicate fp_predicate, void* user_data) {
    if (list_is_empty(pThis) || NULL == fp_predicate)
        return 0;

    int count = 0;
    t_list_node * pNode = pThis->holder.pNext;
    for (int i = 0; i < pThis->length; ++i) {
        if ( fp_predicate(pNode->pValue, user_data) ) {
            ++ count;   --i;
            list_remove(pThis, pNode);
        }
        pNode = pNode->pNext;
    }

    if (0 == pThis->length) {
        pThis->length = 0;
        pThis->holder.pPrev = pThis->holder.pNext = NULL;
    }

    return count;
}



//------------------------------------------------------------------------
//  Operations of class List Iterator
//

// three operations for traverse the list in forward

static t_list_node_ptr iterator_begin(struct list_iterator* pThis) {
    if (NULL == pThis)
        return NULL;
    if ( list_is_empty(pThis->pList) )
        return &(pThis->pList->holder);

    return pThis->pCurrentNode = pThis->pList->holder.pNext;
}

static t_list_node_ptr iterator_end(struct list_iterator* pThis) {
    if (NULL == pThis )
        return NULL;

    return &(pThis->pList->holder);
}

static t_list_node_ptr iterator_next(struct list_iterator* pThis) {
    if (NULL == pThis )
        return NULL;

    if (   list_is_empty(pThis->pList)
        || pThis->pCurrentNode == pThis->pList->holder.pPrev   // last one
        || pThis->pCurrentNode == &(pThis->pList->holder)    )
    {
        return pThis->pCurrentNode = &(pThis->pList->holder);
    }

    if (NULL == pThis->pCurrentNode)
        return pThis->pCurrentNode = pThis->pList->holder.pNext;
    else
        return pThis->pCurrentNode = pThis->pCurrentNode->pNext;
}


// three operations for traverse the list in backward

static t_list_node_ptr iterator_rbegin(struct list_iterator* pThis) {
    if (NULL == pThis )
        return NULL;
    if ( list_is_empty(pThis->pList) )
        return &(pThis->pList->holder);

    return pThis->pCurrentNode = pThis->pList->holder.pPrev;
}

static t_list_node_ptr iterator_rend(struct list_iterator* pThis) {
    if (NULL == pThis )
        return NULL;

    return &(pThis->pList->holder);
}

static t_list_node_ptr iterator_prev(struct list_iterator* pThis) {
    if (NULL == pThis )
        return NULL;
    if ( list_is_empty(pThis->pList) )
        return &(pThis->pList->holder);

    if (list_is_empty(pThis->pList)
        || pThis->pCurrentNode == pThis->pList->holder.pNext    // first one
            || pThis->pCurrentNode == &(pThis->pList->holder)    )
        return pThis->pCurrentNode = &(pThis->pList->holder);

    if (NULL == pThis->pCurrentNode)
        return pThis->pCurrentNode = pThis->pList->holder.pPrev;
    else
        return pThis->pCurrentNode = pThis->pCurrentNode->pPrev;
}



void list_iterator_init(t_list_iterator * pThis, t_list_ptr pList) {
    pThis->pCurrentNode = NULL;
    pThis->pList        = pList;

    pThis->begin  = iterator_begin;
    pThis->end    = iterator_end;
    pThis->next   = iterator_next;

    pThis->rbegin = iterator_rbegin;
    pThis->rend   = iterator_rend;
    pThis->prev   = iterator_prev;
}
